問題

這邊一樣以 AtCoder Educational DP Contest 的類題來舉例，這題是 B - Frog 2，簡單來說一隻青蛙可以一次走 ~ 步，然後每一步的價值就是前面和這一步的高度差，然後要找從第一步到最後一步花費的最低價值

解題思路

可以發現這一題跟昨天相比又有一點不同，他最多可以一次走 步，不過仔細一看發現 ，所以就算你直接枚舉找出走到每一步的最小成本也只會是 而已，而這邊的 是 ，所以乘起來就是 ，完全是可以的範圍

AC Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,k;
    cin >> n >> k;
    vector<long long> stone(n),dp(n,INT_MAX);
    for(int i = 0;i < n;i++){
        cin >> stone[i];
    }
    dp[0] = 0;
    for(int i = 1;i < n;i++){
        for(int j = 1;j <= k;j++){
            if(i - j >= 0){
                dp[i] = min(dp[i - j] + abs(stone[i] - stone[i - j]),dp[i]);
            }
        }
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

時間複雜度

前面有提到會需要枚舉走 步的情況，所以是

總結

由此可知其實 DP 一種經典題就可以改成好幾種形式與延伸，所以要在賽中解出 DP 題只能平常多多練習，或是你有很強的思考能力才有辦法

預告

看起來應該到完賽日都寫不完，不過我認為 AtCoder Educational DP Contest 是很好的題組，包含許多 DP 經典題，可以一題一題練習，我相信這樣的日常練習在賽中會有很大的幫助